Tối ưu hóalà quá trình toán học nhằm tìm ra lời giải "tốt nhất"—tối thiểu hóa hoặc tối đa hóa một hàm mục tiêu—trong một miền khả thi được xác định và bị ràng buộc bởi các quy tắc cụ thể.
Phương pháp Cổ điển so với Phương pháp Thông minh
- Phương pháp Newton-Raphson:Là phương pháp tìm nghiệm lặp sử dụng đạo hàm bậc hai (ma trận Hessian).
- Hạ gradient:Là phương pháp bậc một di chuyển về điểm cực tiểu cục bộ bằng cách đi theo hướng ngược lại của gradient.
- Thuật toán tiến hóa (EAs):Các phương pháp tìm kiếm ngẫu nhiên dựa trên quần thể, lấy cảm hứng từ sự chọn lọc tự nhiên trong sinh học.
Những khái niệm quan trọng
Rất quan trọng khi phân biệt giữaVéc-tơ quyết định (những biến ta thay đổi) vàHàm mục tiêu (tiêu chí thành công).
Những sai lầm trong mã hóa
Hãy cẩn thận với hiện tượnggradient biến mất trong các phương pháp dựa trên vi tích phân vàđáy Hamming trong các thuật toán tiến hóa mã nhị phân. Một bước tăng đơn vị thập phân duy nhất (ví dụ: từ 7 đến 8) có thể yêu cầu đảo ngược tất cả các bit (0111 thành 1000), tạo thành một "vách đá" làm giảm hiệu quả tìm kiếm. Nên sử dụngmã Gray để giảm thiểu điều này.
Triển khai bằng Python: Hạ gradient
Câu hỏi 1
Tại sao bài toán tối ưu hóa lồi được coi là "dễ hơn" bài toán phi lồi?
Câu hỏi 2
Trong ngữ cảnh thuật toán tiến hóa, "kiểu hình" biểu thị điều gì?
Trường hợp nghiên cứu: Tối đa hóa diện tích tam giác
Đọc tình huống dưới đây và trả lời các câu hỏi về việc thiết lập mô hình.
Xét bài toán tối đa hóa diện tích tam giác vuông khi độ dài cạnh huyền $c$ là cố định.
Câu hỏi
1. Xác định các biến quyết định và hàm mục tiêu.
Lời giải:
Biến số: Chiều dài hai cạnh góc vuông, $a$ và $b$.
Hàm mục tiêu: Tối đa hóa $Diện tích = \frac{1}{2} \cdot a \cdot b$.
Biến số: Chiều dài hai cạnh góc vuông, $a$ và $b$.
Hàm mục tiêu: Tối đa hóa $Diện tích = \frac{1}{2} \cdot a \cdot b$.
Câu hỏi
2. Nêu ràng buộc dựa trên tính chất hình học.
Lời giải:
Dựa trên định lý Pythagore, ràng buộc là: $a^2 + b^2 = c^2$.
Dựa trên định lý Pythagore, ràng buộc là: $a^2 + b^2 = c^2$.
Câu hỏi
3. Nếu sử dụng phương pháp Newton-Raphson, ma trận nào phải được tính toán để xét đến các đạo hàm riêng bậc hai?
Lời giải:
Ma trậnHessian ($H$), chứa tất cả các đạo hàm riêng bậc hai của hàm mục tiêu.
Ma trậnHessian ($H$), chứa tất cả các đạo hàm riêng bậc hai của hàm mục tiêu.